Relative neighborhood graphs (RNGs) and their variants, such as Gabriel graphs, have been proposed as methods for connecting a set of points by edges so that the resulting graph characterizes the perceived shape of the point-set. Both RNGs and Gabriel graphs are special cases of general shape-encoding graph constructs called β-skeletons. Relative neighborhood graphs can play an important role in a variety of applications, such as morphological processing in computer vision, pattern classification problems, geographical analysis, and wireless networking.
In spite of the utility of RNGs and the potential for their application in a variety of important fields, computation of cycle lengths and perimeters of RNGs becomes extremely difficult as the size of the problem increases (e.g., whole-mount histopathology slides, large-scale wireless networks spanning a continent, star systems, etc.). In the case of histopathological image analysis, there are significant computational challenges involved in studying correlations between macroscopic imaging biomarkers—for example, MR data—and histopathological network cycle features—for example, a prostatectomy whole-mount slide—because the computations involve several thousand MR voxels and several million nuclei. Moreover, an MR voxel maps onto an irregular region in histopathological slides due to various deformations (e.g., expansion after prostatectomy, tissue cuts and tears during microtome use, tissue dehydration during staining, etc.) involved in the process, such that computation of the average network cycle lengths over an irregular region becomes necessary.